package Airpot;

import java.util.*;

////332. 重新安排行程

public class A {

    public static void main(String[] args) {
        String[][] a = {{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}};
        Solution s = new Solution();
        List<List<String>> t = new LinkedList<>();
        for (int i = 0; i < a.length; i++) {
            List<String> bb = new LinkedList<>();
            for (int j = 0; j < a[i].length; j++) {
                bb.add(a[i][j]);
            }
            t.add(bb);
        }
        s.findItinerary(t);
    }
}

/**
 * 欧拉图的一笔画问题
 */
class Solution {
    Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> itinerary = new LinkedList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0);
            String dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).add(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    /*
        不需要回溯
        。。。。欧拉图的遍历算法
        从起点开始dfs
        在没节点可以遍历的时候就把这个节点加入到list种
        最后逆序就是最后的一笔画结果
     */
    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        itinerary.add(curr);
    }
}

